Sqrt(x)

Time: O(LogN); Space: O(1); medium

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4

Output: 2

Example 2:

Input: 8

Output: 2

Explanation:

  • The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.

Example 3:

Input: 0

Output: 0

Example 4:

Input: 3

Output: 1

Explanation:

  • Return the largest integer y that y*y <= x.

Hints:

  1. Try exploring all integers.

  2. Use the sorted property of integers to reduced the search space.

1. Binary Search [O(LogN),O(1)]

[6]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 2:
            return x

        left, right = 1, x // 2

        while left <= right:
            mid = left + (right - left) // 2
            if mid > x // mid:
                right = mid - 1
            else:
                left = mid + 1

        return left - 1

[7]:

s = Solution1()

x = 4
assert s.mySqrt(x) == 2

x = 8
assert s.mySqrt(x) == 2

x = 0
assert s.mySqrt(x) == 0

x = 3
assert s.mySqrt(x) == 1